package ShortestPathDemo;


/**
 * 二维矩阵 存储方式
 */

public class TwoDimensionalMatrixDemo {

    /**      1  2  3  4  5  6  7
     *     * *  *  *  *  *  *  *
     *   1 * 0  3  ∞  2  5  ∞  ∞
     *   2 * 3  0  2  ∞  1  ∞  ∞
     *   3 * ∞  2  0  ∞  4  ∞  4
     *   4 * 2  ∞  ∞  0  3  5  ∞
     *   5 * 5  1  4  3  0  1  ∞
     *   6 * ∞  ∞  ∞  5  1  0  3
     *   7 * ∞  ∞  4  ∞  ∞  3  0
     */
    final static int max = 9999;
    static int[] poings = {1,2,3,4,5,6,7}; //点的集合数组
    //任意两点之间的权重 ，无向图
    static int[][] pathArray = {  {0, 3, max, 2, 5, max, max},
                            {3, 0,  2, max, 1, max, max},
                            {max,2, 0, max, 4, max,   4},
                            {2, max,max, 0, 3 , 5,  max},
                            {5,  1,  4,  3 , 0,  1,  max},
                            {max, max, max, 5, 1, 0, 3},
                            {max, max, 4, max, max,3, 0}};

    static int[] book = null;  //从起始点到当前点，已确定最短距离的点
    static int[] distinct = null; //从起始点到当前点的距离   临时量，随着程序的执行，此值会改变
    static int INF = -1;

    //Dijkstra算法
    public static void dijkstra(int startPoint){
        //初始化
        for(int i = 1; i <= poings.length; i++){
            distinct[i] = pathArray[startPoint-1][i-1]; //初始化distinct为源点到各点的距离
        }
        for(int i = 1; i <= poings.length; i++){
            book[i] = 0;  //0：代表此下标指定的点 未确定
        }
        book[startPoint] = 1 ; //初始时P集合中只有源点 1：代表已确定

        //做n-1遍就能把Q遍历空
        int u = 0;
        for(int i = 1; i <= poings.length-1; i++) {
            int min = INF;

            for(int j = 1; j <= poings.length; j++){ //寻找Q中最近的结点
                if(book[j] == 0 && distinct[j] < min) {
                    min = distinct[j];
                    u = j;
                }
            }
            book[u] = 1; //加入到P集合
            for(int v = 1; v <= poings.length; v++) { //对u的所有出边进行松弛
                if(pathArray[u][v] < INF) {
                    if(distinct[v] > distinct[u] + pathArray[u][v])
                        distinct[v] = distinct[u] + pathArray[u][v];
                }
            }
        }
    }


    //Floyd算法
    public static void floyd(int startPoint){
        int[][] path = new int[poings.length][poings.length];
        int[][] dist = new int[poings.length][poings.length];

        // 初始化
        for (int i = 0; i < poings.length; i++) {
            for (int j = 0; j < poings.length; j++) {
                dist[i][j] = pathArray[i][j];    // "顶点i"到"顶点j"的路径长度为"i到j的权值"。
                path[i][j] = j;                // "顶点i"到"顶点j"的最短路径是经过顶点j。
            }
        }
        // 计算最短路径
        for (int k = 0; k < poings.length; k++) {
            for (int i = 0; i < poings.length; i++) {
                for (int j = 0; j < poings.length; j++) {
                    // 如果经过下标为k顶点路径比原两点间路径更短，则更新dist[i][j]和path[i][j]
                    int tmp = (dist[i][k]==max || dist[k][j]==max) ? max : (dist[i][k] + dist[k][j]);
                    if (dist[i][j] > tmp) {
                        // "i到j最短路径"对应的值设，为更小的一个(即经过k)
                        dist[i][j] = tmp;
                        // "i到j最短路径"对应的路径，经过k
                        path[i][j] = path[i][k];
                    }
                }
            }
        }


        for (int i = 0; i < poings.length; i++) {
            for (int j = 0; j < poings.length; j++) {
                System.out.print(dist[i][j] + ",");
            }
            System.out.println();
        }
        System.out.println("================================");
        for (int i = 0; i < poings.length; i++) {
            for (int j = 0; j < poings.length; j++) {
                System.out.print(path[i][j] + ",");
            }
            System.out.println();
        }

        StringBuilder sb = new StringBuilder(startPoint +"点到其他点的距离：");
        for (int i = 0; i < poings.length; i++) {
           sb.append("到"+ (i+1) +"点的距离=" + dist[startPoint-1][i] +";路径：");
           StringBuilder paths = new StringBuilder(startPoint+"");
           int a = startPoint-1;
           while(path[a][i] != i){
               paths.append("-->" + (path[a][i] + 1) );
               a = path[a][i];
           }
            paths.append("-->" + (i+1));

           sb.append(paths);
        }

        System.out.println("floyd算法" + sb);

    }

    public static void main(String[] args) {
        floyd(1);
    }







}
